package com.jzoffer;

import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/*
* 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向
* */
public class BinaryTreeAndLinkedList {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(5);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(2);
//        TreeNode t4 = new TreeNode(4);
//        TreeNode t5 = new TreeNode(6);
        TreeNode t6 = new TreeNode(7);
//        TreeNode t7 = new TreeNode(8);
//        TreeNode t8 = new TreeNode(9);
//        TreeNode t9 = new TreeNode(10);
        t1.left = t2;
        t1.right = t6;
        t2.left = t3;
//        t2.right = t4;
//        t6.left = t5;
//        t6.right = t8;
//        t8.left = t7;
//        t8.right = t9;
        TreeNode res = Convert(t1);

        List<Integer> list = RebuildBinaryTree.preOrder(res);
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()){
            Integer next = iterator.next();
            System.out.println(next);
        }

    }

    public static TreeNode Convert(TreeNode pRootOfTree){
        if(pRootOfTree == null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode result = null;

        // 当栈非空 或者当前有结点指向时
        while (!stack.isEmpty() || pRootOfTree != null){
            // 如果当前有指针指向树中结点，那么向栈中添加，并访问右子树
            if(pRootOfTree != null){
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.right;
            }else{
                // 如果没有右子树的时候
                // 当第一次构建时，判断
                pRootOfTree = stack.pop();
                if (result == null){
                    result = pRootOfTree;
                }else{
                    // 当前结点一定比result指向的结点小，因此改变结点指向
                    result.left = pRootOfTree;
                    pRootOfTree.right = result;
                    //设置当前值
                    result = pRootOfTree;
                }
                // 取左节点按照上述操作
                pRootOfTree = pRootOfTree.left;
            }
        }
        return result;
    }
}
